package com.justnow.offer;

import java.util.LinkedList;

public class Solution104 {

    /**
     * 方法一，递归,DFS
     *
     * 时间复杂度：每个节点只访问一次，因此时间复杂度为O(N)
     * 空间复杂度：在最糟糕的情况下，树是完全不平衡的，例如每个节点只剩下左子节点，递归将会调用N次，因此保持调用栈的存储将是O(N)。
     * 但是在最好的情况下（树是完全平衡的），树的高度将是log(N)。因此，在这种情况下的空间复杂度将是O(log(N))
     * @param root
     * @return
     */
    public int maxDepth01(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            //只看根节点和其左右子节点，那么下面三行程序就是正确的结果
            int left_height = maxDepth01(root.left); //返回根节点的左子树的高度
            int right_height = maxDepth01(root.left);//返回根节点的右子树的高度
            return Math.max(left_height, right_height) + 1; //根节点为左子树高度和右子树高度最大者，加1
        }
    }

    /**
     * 方法二，迭代，BFS层次遍历思想
     * 时间复杂度O(n)
     * 空间复杂度：线性表最差O(n)、二叉树完全平衡二叉树最后，O(logn)
     * @param root
     * @return
     */
    public int maxDepth02(TreeNode root) {
        if (root == null){
            return 0;
        }
        //BFS的层次遍历，记录二叉树的层数
        //遍历完，层数即为最大深度
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int maxDepth = 0;
        while (!queue.isEmpty()) {
            maxDepth++;
            int levelSize = queue.size();//在本层的节点的个数
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.pollFirst(); //循环一次移除一个节点，并且将其左右子节点存入到队列中（如果存在的话）！
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            //循环结束后，queue中存放的是下一层的内容
        }
        return maxDepth;
    }

    public static void main(String[] args) {
        Solution104 solution104 = new Solution104();
    }


}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}